home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / CIS_GAME.ARJ / QPOLY1.THD < prev    next >
Text File  |  1993-06-25  |  62KB  |  1,302 lines
  1. ________________________ Subj: Centroid of a Polygon ________________________
  2.  
  3. Fm: Chris Lampton [GAMPUB] 76711,301           # 173393 
  4. To: John M. Dlugosz 70007,4657 (X)             Date: 31-May-92  17:42:31
  5.  
  6. The centroid is the point at which the polygon would balance were it a flat
  7. plate with evenly distributed weight. It's apparently fairly common to base
  8. priority sorts on the centroid rather than maximum and minimum z, though very
  9. few graphics books discuss it. (Abrash's does, but only briefly.) I'm finally
  10. beginning to understand why the centroid is used -- it produces the best
  11. first approximation of any method of priority sort -- and want to switch my
  12. hidden surface routines to use it, but don't want to sit here and figure it
  13. out by eyeball guess on every polygon.
  14.  
  15. Maybe if I sit down and think about it, I can come up with an algorithm (but
  16. I'm not going to be money on it.) What was the "other graphics book" that
  17. mentioned it?
  18.  
  19. --Chris
  20. ...........................................................................
  21.  
  22. Fm: Everett Kaser (Sherlock) 70673,1547        # 173494 
  23. To: Chris Lampton [GAMPUB] 76711,301 (X)       Date: 31-May-92  22:15:06
  24.  
  25. Well, I'm not a mathematician, and I haven't gone to the extent of designing
  26. an algorithm or writing any code (wouldn't want to take the fun away from
  27. you! <g>), but putting a little of my old geometry together with a little of
  28. my college physics, here's how it seems to me:
  29.  
  30. You CAN find the centroid of a triangle by drawing two of the triangle's
  31. medians (the lines that bisect the angles of the triangle), since all three
  32. medians of a triangle ALWAYS intersect together at the centroid.
  33.  
  34. So, let's say that you pick a vertex of your convex polygon and draw a line
  35. from it to every other vertex of the polygon except for its neighbors on
  36. either side.  This divides the polygon up into a bunch of triangles (n-2,
  37. where n is the number of vertices).  You can now find the centroid of each of
  38. these individual triangles quite easily.  This gives you a list of "centers
  39. of gravity" for the triangles, which together, comprise the "weight" of the
  40. entire polygon.  So, (he says off-handedly) all that's left is to find the
  41. center of gravity for these centroids.  (Here's where the college physics
  42. comes in:  you can treat the mass of an object AS IF the entire mass exists
  43. as a point at the mass's center of gravity.  Hence, why I think this scheme,
  44. or something similar will work here.) 
  45.  
  46. Here's where I'm not quite as certain of the accuracy, but it LOOKS right on
  47. the couple of test cases I tried.
  48.  
  49. Take the center of gravity for one of the triangles on the "outside", to
  50. either side of the "central" vertex (from which you drew all the lines in the
  51. first part).  Now, draw a line from it to the other "outside" triangle on the
  52. other side of the "central" vertex.  Then, use then next vertex in (from the
  53. second "outside" center of gravity) as the third point of a triangle, and
  54. draw the other two sides of this first "center of gravity" triangle.  Now use
  55. that "third point" from the previous sentence with the
  56. first "outside" center of gravity point and the next center of gravity point
  57. over, to form the next triangle.  Just keep adding one more centroid to form
  58. each successive triangle until you run out of centroids.  You now have a new
  59. set of triangles, but one less than you did before.  You now find the
  60. centroids for each of these triangles.  Repeat until you're down to one
  61. triangle, and it's centroid is the centroid for the entire polygon.
  62.  
  63. Now, in all likelihood, that's all wrong, the centroid is elsewhere, and
  64. there's an easier way of finding the center of gravity for a collection of
  65. masses (the centroids for the FIRST set of triangles).  I don't remember THAT
  66. much of my college physics.
  67.  
  68. Anyway, maybe that will help some, and thanks for the puzzler.
  69.  
  70. Everett
  71. ...........................................................................
  72.  
  73. Fm: Chris Lampton [GAMPUB] 76711,301           # 173677 
  74. To: John M. Dlugosz 70007,4657 (X)             Date: 01-Jun-92  13:06:53
  75.  
  76. Oddly, I've found that the centroid (or something approximating it) tends to
  77. work better in a lot of real world situations than the minimum or maximum z,
  78. though this may be the result of biased data. Consider a pyramid constructed
  79. from four triangles and a square, with the triangles coming to a point at one
  80. end and the square at the other end as the base. Turn off backface removal.
  81. (Okay, that makes the situation a tad unrealistic, but stick with me.) Use a
  82. simple depth sort on the maximum z. Point the tip of the pyramid more than 90
  83. degrees away from the viewer. Every triangle in the pyramid has the same
  84. maximum z, so the sort will be essentially random and hidden surfaces will
  85. show through. Now switch to a simple depth sort on the minimum z. Rotate the
  86. point of the pyramid less than 90 degrees from the viewer. Same problem. But
  87. use the centroid and the sort is correct in both situations. Only when the
  88. point of the pyramid is aimed directly at the viewer, or directly away, do
  89. all of the triangles have the same centroid distance -- and then it's
  90. irrelevant, since none of the triangles occludes any of the others.
  91.  
  92. Of course, backface removal normally takes care of this, so it may not be
  93. entirely necessary. Still, the centroid does seem useful. Unless you can
  94. think of some situations that contradict these.
  95.  
  96. --Chris
  97. ...........................................................................
  98.  
  99. Fm: John M. Dlugosz 70007,4657                 # 173750 
  100. To: Chris Lampton [GAMPUB] 76711,301 (X)       Date: 01-Jun-92  16:39:34
  101.  
  102. I think I see your point.  The min or max z sorting does not work right when
  103. polygons share commen edges, in particular.  I discovered this a few months
  104. ago.  Using _any_ interior point of the z extent would overcome this.  I
  105. think I'll try sorting on the midpoint of z.
  106.  
  107. BTW, how do you handle the 5th test of the painter's algorythm?
  108.  
  109. --John
  110. ...........................................................................
  111.  
  112. Fm: Chris Lampton [GAMPUB] 76711,301           # 173768 
  113. To: John M. Dlugosz 70007,4657 (X)             Date: 01-Jun-92  17:37:09
  114.  
  115. I'm about to try a method that does away with extents and overlap tests
  116. altogether, which may or may not work. I'll sort on the distance of the
  117. center of the extent, calculated as:     
  118.  
  119. CENTER_X*CENTER_X+CENTER_Y*CENTER_Y+CENTER_Z*CENTER_Z
  120.  
  121. After sorting, I'll draw the polygons, without further swaps. If the scenery
  122. is designed correctly, and backface removal is performed before the depth
  123. sorts, pathological cases should only arise occasionally during animation.
  124. With luck, they'll only arise so briefly that nobody will notice.
  125.  
  126. The trouble with checking overlapping extents is that you run into a
  127. combinatorial explosion. You have to compare the extents of every polygon
  128. with every other polygon, so that the number of comparisons equals the number of
  129. polygons _squared_. Put too many polygons in a scene and even brief extent
  130. comparisons begin to overload the system and slow down the frame rate, never
  131. mind the additional tests when the extents overlap.
  132.  
  133. If it looks like crap, of course, I'll be re-implementing the extent checks
  134. and the five tests. *Groan*
  135.  
  136. --Chris
  137. ...........................................................................
  138.  
  139. Fm: John M. Dlugosz 70007,4657                 # 173796 
  140. To: Chris Lampton [GAMPUB] 76711,301 (X)       Date: 01-Jun-92  18:50:43
  141.  
  142. I don't get it.  The center's distance from the origin (in eye co-ordinates I
  143. take it) will not define a sort order.  That is just the initial ordering,
  144. and I don't see how that is better than just looking at the Z distance.
  145. Picture an object that is up in the corner (so x and y are large) and z is
  146. some value.  Now compare that with an object centered at x,y but has a large
  147. Z value, but still sorts smaller because x and y are zero.  You will draw
  148. that one second even though it is behind the large near object in the corner.
  149.  
  150. In general, polygons can overlap in interesting ways.  The only way to tell
  151. which is in front is by testing a point that is common to the projections of
  152. both and seeing which is nearer.  The first 4 tests of the painter's
  153. algorythm have smaller big-oh's which is why they are there. But they don't
  154. always work. 
  155.  
  156. Testing the extents is one of the first tests.  that is cheap.  And you don't
  157. test everyone against everyone else-- only a pair of neighboring polygons
  158. after the initial sorting.
  159.  
  160. Anyway, I plan on writing mine tonight.  Was just wondering about test 5.
  161. I'll do that one only, first, to make sure it works right.  Then I'll add the
  162. others to speed it up.  The hard part is finding a point common to both
  163. projections. 
  164.  
  165. --John
  166.  
  167. ____________________________ Subj: Polygon Stuff ____________________________
  168.  
  169. Fm: Chris Lampton [GAMPUB] 76711,301           # 173876 
  170. To: John M. Dlugosz 70007,4657 (X)             Date: 01-Jun-92  20:36:46
  171.  
  172. I'm experimenting with several methods of sorting to see which produces the
  173. best result. Using the true distance from the origin rather than the z
  174. coordinate may or may not prove superior; I'll decide after I've played with
  175. it a bit.
  176.  
  177. Hmm, are you sure that you can get away with only comparing neighboring
  178. polygons in the sorted list? It's possible for polygons quite distant from
  179. one another in the list to overlap in extent. But perhaps at least one of the
  180. overlapping polygons would also overlap the extents of the polygons in
  181. between the two, so that you could make multiple passes through the list,
  182. bringing the overlapping polygons closer and closer together, bubble-sort
  183. fashion, until no more swaps are necessary. I'll have to think about that.
  184. (Or is that what you had in mind all along?) 
  185.  
  186. --Chris
  187. ...........................................................................
  188.  
  189. Fm: Chris Lampton [GAMPUB] 76711,301           # 174051 
  190. To: John M. Dlugosz 70007,4657 (X)             Date: 02-Jun-92  10:33:00
  191.  
  192. >If the painter's algorythm makes you exchange two items, you then re-test in
  193. the new position.
  194.  
  195. Wait a minute, does that work? Consider the following case:
  196.  
  197.  
  198.                                     /
  199.                                    /
  200.                                   /
  201.                                  /       
  202.                               1 /
  203.        /                       /
  204.     2 /                       /
  205.      /                       /
  206.     /                       /
  207.                            /
  208.                           /
  209.                          /
  210.                         /
  211.                  /     /
  212.               3 /     /
  213.                /     /
  214.               /     /
  215.                    /
  216.                   /
  217.                  /
  218.                 /
  219.                /            ^
  220.                             |
  221.                             |
  222.                             |
  223.                                         Viewer
  224.  
  225.  
  226. If these three polygons (seen edge on from above, looking down the y axis,
  227. with the viewer at the bottom) are sorted by maximum z, they'll end up sorted
  228. in the numeric order seen here. Assume that all three polygons have
  229. overlapping y extents. Polygon 1's z extent overlaps the other two polygons.
  230. Polygon 3 should be occluded by 1, but will be drawn over top of 1. The
  231. solution is to swap 3 and 1. Yet if only adjacent pairs are swapped, no swaps
  232. will occur, because neither 1 and 2 nor 2 and 3 overlap in the x extent. Or
  233. are polygons swapped merely because they overlap in the z extent, for
  234. purposes of further comparison?
  235.  
  236. --Chris
  237. ...........................................................................
  238.  
  239. Fm: John M. Dlugosz 70007,4657                 # 174145 
  240. To: Chris Lampton [GAMPUB] 76711,301 (X)       Date: 02-Jun-92  14:24:57
  241.  
  242. According to Foley,
  243.  
  244. "let the polygon at the far end of the sorted list of polygons be called P.
  245. Before it is scan converted, it must be tested against each polygon Q whose z
  246. extend overlaps P, to prove that P cannot obscure P. ... as soon as one
  247. succeeds, P has been show not to obsucre P.
  248.  
  249. OK, so sort by max Z.  Then start with 1, and compare it with each element in
  250. the list whose extent overlaps it.  Those will be the following n objects,
  251. until the max z of an object is less than the min z of the current object.
  252.  
  253. If it fails one of the tests, than (assuming the polygons don't have cyclic
  254. overlaps), reposiiton P to just after the one that overlaps it and start over
  255. with the new top of the list.  (the full way is to split the polygon)
  256.  
  257. There is more to it... new versions of tests 3 and 4 after swapping the
  258. polygons, to find out if they can be simply reversed or need to be split.
  259.  
  260. --John
  261. ...........................................................................
  262.  
  263. Fm: Chris Lampton [GAMPUB] 76711,301           # 174156 
  264. To: John M. Dlugosz 70007,4657 (X)             Date: 02-Jun-92  15:09:17
  265.  
  266. Incidentally, I'm having a little trouble envisioning how one avoids going
  267. into an infinite loop if cyclic overlap occurs, given that one isn't
  268. splitting polygons. Foley suggests setting a flag to prevent two polygons
  269. from being swapped more than once, but I'm not clear as to how this flag is
  270. to be interpreted. As "don't swap this polygon again with the polygon
  271. immediately ahead of it in the list"? Or "don't swap this polygon again with
  272. the polygon at the head of the list"? Or are both interpretations wrong?
  273.  
  274. --Chris
  275. ...........................................................................
  276.  
  277. Fm: yngvi 76703,3046                           # 173705 
  278. To: Everett Kaser (Sherlock) 70673,1547 (X)    Date: 01-Jun-92  14:13:34
  279.  
  280. Right, the centroid calculation is very similar to center of mass with the
  281. assumption that mass is normalized to 1.
  282. ...........................................................................
  283.  
  284. Fm: peter singer 100024,1603                   # 176331 
  285. To: John M. Dlugosz 70007,4657 (X)             Date: 09-Jun-92  16:36:37
  286.  
  287. Yes, there always exist a 'ballancing point'.  Consider you have objects of
  288. different mass on the tray the 'bp' _moves_ to the object with highest mass
  289. at most, to the object with the 2nd highest mass at 2nd most and so on.
  290. Calculating something like 'distance' times 'mass of the object'. Consider
  291. you have 3 objects named A, B, C on 2D axis system. The 3 Objects have the
  292. masses  A_, B_ and C_, the Ballancing Point is named Bp and have the coords
  293. (Bpx,Bpy). 
  294.  
  295.      Y
  296.      :
  297.      :
  298.      :         C(10,6)
  299.      :
  300.      :
  301.      :
  302.      :   A(4,2)
  303.      :                    B(21,1)
  304.      :.....................................X
  305.  
  306. Bpy=(A_*2+B_*1+C*6)/(A_+B_+C_) Bpx=(A_*4+B_*21+C_*10)/(A_+B_+C_)
  307.  
  308. This can be done by any number of _static_ objects! If the axis _cross_
  309. through the objects you have to change the sign.
  310.  
  311. The easiest way to ballance a tray is to place the haviest object in the
  312. center. Hope this helps... PSi.
  313. ...........................................................................
  314.  
  315. Fm: John M. Dlugosz 70007,4657                 # 176424 
  316. To: peter singer 100024,1603 (X)               Date: 09-Jun-92  21:18:08
  317.  
  318. I picked weights C=10, A=15, and B=20.  After finding the point via your
  319. formula (150/45 , 12), I found the sum of the cross products between the
  320. weights (vector is [0 0 weight]) and the vector from the ballance point (p -
  321. [150/45,12,0]).  I got a sum of [-430, -430, 0].  I was expecting all zeros. 
  322. What is the significance of this?
  323.  
  324. --John
  325. ...........................................................................
  326.  
  327. Fm: peter singer 100024,1603                   # 176677 
  328. To: John M. Dlugosz 70007,4657 (X)             Date: 10-Jun-92  16:32:26
  329.  
  330.  
  331. >I picked weights C=10, A=15, and B=20.  After finding the point via your
  332. >formula (150/45 , 12), I found the sum of the cross products between the
  333.           ^^^^^^^????? >weights (vector is [0 0 weight]) and the vector from
  334. the ballance point (p - >[150/45,12,0]).  I got a sum of [-430, -430, 0].  I
  335. was expecting all zeros.
  336.  
  337. You missed something...there are no vectorisations! I think you can also
  338. calculate this way the point of balance og a polygon using for the corner a
  339. weight of 1 and the corner coords.
  340.  
  341. Just simply calculation:
  342.  
  343. A+B+C= 45 Bpy= (15*2+20*1+10*6)/45=    2.44444444444444444 Bpx=
  344. (15*4+20*21+10*10)/45= 12.88888888888888888
  345.  
  346. If you now lay the axis through Bpx/Bpy you get following coords:
  347. A(8.89/-0.44)  B(8.11/-1.44)   C(-2.89/3.56)
  348.  
  349. Do now calculation of the weigths:
  350.  
  351. for the x-axis: 15*(-0.44)+20*(-1.44)+10*3.56 = 0.2 --> 0! rounding diff.
  352.         y-axis: 15*(-8.89)+20*8.11+10*(-2.89) = 0.05 --> 0! rounding diff.
  353.  
  354. Is the fog away??? PSi.
  355. ...........................................................................
  356.  
  357. Fm: peter singer 100024,1603                   # 176676 
  358. To: John M. Dlugosz 70007,4657 (X)             Date: 10-Jun-92  16:32:12
  359.  
  360. Yes, there always exist a 'ballancing point'.  Consider you have objects of
  361. different mass on the tray the 'bp' _moves_ to the object with highest mass
  362. at most, to the object with the 2nd highest mass at 2nd most and so on.
  363. Calculating something like 'distance' times 'mass of the object'. Consider
  364. you have 3 objects named A, B, C on 2D axis system. The 3 Objects have the
  365. masses A_, B_ and C_, the Ballancing Point is named Bp and have the coords
  366. (Bpx,Bpy).  
  367.  
  368.      Y
  369.      :
  370.      :
  371.      :         C(10,6)
  372.      :
  373.      :
  374.      :
  375.      :   A(4,2)
  376.      :                    B(21,1)
  377.      :.....................................X
  378.  
  379. Bpy=(A_*2+B_*1+C*6)/(A_+B_+C_) Bpx=(A_*4+B_*21+C_*10)/(A_+B_+C_)
  380.  
  381. This can be done by any number of _static_ objects! If the axis _cross_
  382. through the objects you have to change the sign.
  383.  
  384. The easiest way to ballance a tray is to place the haviest object in the
  385. center. Hope this helps... PSi.
  386.  
  387. _________________________ Subj: Texture Mapping _________________________
  388.  
  389. Fm: KGliner 70363,3672                         # 343391 
  390. To: John Dlugosz [ViewPoint] 70007,4657 (X)    Date: 28-Apr-93  12:52:53
  391.  
  392. John-  what's there to say about texture-mapping?  Wolfenstein and Ultima
  393. Underworld.  The former uses a ray-casting approach, and the latter is
  394. polygon based.  Using polygons is probably an easier approach for a graphics
  395. library: given a 4-sided convex polygon, map a square bitmap onto it (ie.
  396. where the four corners of the bitmap are stretched to fit into the four
  397. corners of the polygon). Where it gets complicated (especially with multiple
  398. polygons) is that you never want to draw a pixel to the same location twice
  399. (or as infrequently as possible). And even then you don't want to be
  400. executing more than about 5 to 8 assembly language instructions per pixel
  401. (and we're talking mov and add only).  Any graphics library that could pull
  402. this off with any semblance of speed I'd buy in a heartbeat (as would many
  403. others, I imagine). 
  404.  
  405.   Kevin
  406. ...........................................................................
  407.  
  408. Fm: John Dlugosz [ViewPoint] 70007,4657        # 343879 
  409. To: KGliner 70363,3672 (X)                     Date: 29-Apr-93  00:17:13
  410.  
  411. Texture mapping as you describe sounds like a transformation applied to a
  412. bitmap.  My own efforts in this area are designed to produce high quality
  413. results.  For mapping, you want fast results.
  414.  
  415. Mapping a bitmap to a polygon, you can have to stretch it or shrink it. In
  416. the former, one bitmap pixel mapps to several target pixels.  In the latter,
  417. some bitmap pixels go unused.  Is that what you have in mind?
  418.  
  419. Anyone here want to discuss techniques?  Let's start with theory.
  420.  
  421. --John
  422. ...........................................................................
  423.  
  424. Fm: Lutz Kretzschmar 100023,2006               # 344108 
  425. To: John Dlugosz [ViewPoint] 70007,4657 (X)    Date: 29-Apr-93  11:40:10
  426.  
  427. I've written similar code for a client in the image processing segment. I
  428. used a technique similar to Abrash' in Dr Dobbs. The major stress was on
  429. quality and it works with 24-bit Truecolor bitmaps at 1024x768 resolution, so
  430. it may not apply to game design, in terms of speed<g>.
  431.  
  432. When scan converting a polygon, setup four bresenhams (or similar
  433. line-walkers), two for the polygon edges of the scan converter and two
  434. corresponding ones in the texture space. The ones in the texture space using
  435. the step amount of the screen polygon walkers. Then at each scanline, setup a
  436. new line-walker that walks across the texture map. It must use the same
  437. amount of steps as the two edge-walkers in screen space are apart. Then step
  438. across the polygon retrieving the color from the texture at the position
  439. indicated by the texture walker, and putting it at the right screen position.
  440. (Did anyone understand that??<g>).
  441.  
  442. Let me try that in ASCII >groan<:
  443.  
  444.       Screen space        A
  445.       Polygon           /   \                  c--------------a
  446.                       /      \                 |              |
  447.                     /         \                |              |
  448.                   /            \               |              |
  449.                 /               B              d--------------b
  450.               /                /
  451.             C--              /                  Bitmap to map
  452.                 ----       /                    onto Polygon
  453.                      --- D
  454.  
  455. Mapping the bitmap abcd onto the polygon ABCD: Setup linewalker along AC and
  456. AB to do the major stepping along y axis. Setup linewalker along ac, using
  457. same number of steps that AC is using. Setup linewalker along ab, using same
  458. number of steps as AB.
  459. In loop of scanlines, step along AC, AB (for screen coords), and along ac and
  460. ab for texture coords. Setup a linewalker for the texture space that goes
  461. from current ac position to current ab position using distance in x that AB
  462. and AC are apart, for number of steps. Retrieve pixels along this linewalker
  463. and place in consecutive x positions on screen.
  464.  
  465. I hope this is understandable<g>. The implementation was written using Fixed
  466. Point arithmetic and is reasonably fast, although much too slow for games, I
  467. should think.
  468.  
  469. This approach does not take into account any perspective foreshortening,
  470. though, since it uses linear mapping across the polygon.
  471.  
  472. I'd be interested in other methods and theories behind texture mapping, too.
  473.  
  474. - Lutz
  475. ...........................................................................
  476.  
  477. Fm: KGliner 70363,3672                         # 344272 
  478. To: Lutz Kretzschmar 100023,2006 (X)           Date: 29-Apr-93  16:19:28
  479.  
  480. Lutz-  I used a similar technique a while back, only I used linewalkers along
  481. opposite edges as opposed to adjacent edges.  I did try a method using
  482. adjacent edges that had it drawing only vertical lines in the polygon, but I
  483. got distortion every time the linewalkers hit a corner.  The whole reason for
  484. trying to draw vertical lines in the polygon is that it both speeds things up
  485. (not to mention you only draw one pixel per location on the screen) and makes
  486. it easier to do hidden surface removal too. 
  487.  
  488.    Kevin
  489. ...........................................................................
  490.  
  491. Fm: Lutz Kretzschmar 100023,2006               # 344303 
  492. To: KGliner 70363,3672 (X)                     Date: 29-Apr-93  17:13:41
  493.  
  494. Kevin,
  495.  
  496. > only I used linewalkers along opposite edges as opposed to adjacent
  497. > edges.
  498. Huh? How does that work? If the polygon in my last message sits in screen
  499. space the way it's drawn, then how can you scan convert it by going along
  500. opposite edges? Do you then do the interpolation at an angle to the screens
  501. coordinate system?
  502.  
  503. > but I got distortion every time the linewalkers hit a corner.
  504. Hmm, I don't get any distortion there.
  505.  
  506. > The whole reason for trying to draw vertical lines in the polygon is that
  507. > it both speeds things up...
  508. Now that again is contrary to what I have always believed<g>. All frame
  509. buffers I know of are best accessed horizontally, because the pixels occupy
  510. sequential addresses. Is this for some special mode? Or are you smarter than
  511. we all are?<g>
  512.  
  513. > (not to mention you only draw one pixel per location on the screen)
  514. Hmm, the method I described does just that, since the scan converter only
  515. generates the pixels that the polygon itself will occupy on the screen. And
  516. only for those does it access the texture map.
  517.  
  518. > ... and makes it easier to do hidden surface removal too.
  519. Can you elaborate a bit<g>? What advantage do verticals have over
  520. horizontals? 
  521.  
  522. - Lutz
  523. ...........................................................................
  524.  
  525. Fm: KGliner 70363,3672                         # 344951 
  526. To: Lutz Kretzschmar 100023,2006               Date: 30-Apr-93  15:38:31
  527.  
  528.   I can see I tried to cram too much into too short a message for it to be
  529. clear.  What I really need is a few charts, e`,ZX6kboard, multi-color graphs,
  530. and lots of fancy symbols.<g>
  531.  
  532.     Anyway, I take it you move through your destination polygon by doing one
  533. horizontal scanline at a time?  I tried an approach like this (only using
  534. vertical scanlines-- more on this in a sec), only I got a distortion at the
  535. corners.  It would appear I didn't pursue it far enough, as you evidently got
  536. it to work.  I'd be very interested to see what you did.
  537.  
  538.     What I ended up doing was running a diagonal (well, non-vertical and
  539. non-horizontal) line through the destination polygon and horizontal lines
  540. through the source bitmap.  This worked, but there were too many wasted
  541. pixels. Oh-- for this approach I also switched to using opposite edges (ie.
  542. run my line walkers from corner A to corner D and from corner B to corner C,
  543. where the order of the points in the bitmap is A-B-C-D).
  544.  
  545.   Now for the whole vertical line bit.  I use a buffer in conventional memory
  546. to do all my 3d calculations on.  Once I've done them all, I want to be able
  547. to move the whole thing to video as fast as possible (copying each horizontal
  548. scanline in multi-byte chunks to the card).  However, before that I want to
  549. draw to the buffer using vertical lines because:  A) most dungeon crawl games
  550. are only concerned with yaw rotation, making it possible to do fast
  551. optimizations for any surfaces that are 'vertical' (ie. the walls in both
  552. Wolfentstein and Ultima Underworld...this doesn't speed up or slow down the
  553. other surfaces [like floors]);  B) each pixel has to be addressed
  554. individually anyway (so word or dword writes are pointless), which makes the
  555. amount of the increment irrelevant (incrementing by the width of the screen
  556. takes just as long as incrementing by 1); and C) it helps with hidden surface
  557. removal  (a whole discussion in itself that I'll hold off on for now).
  558. ........................................................................... 
  559.  
  560. Fm: E. Pinnell [CyberSim] 70031,435            # 344801 
  561. To: KGliner 70363,3672 (X)                     Date: 30-Apr-93  09:46:34
  562.  
  563. Kevin,
  564.  
  565.    I assumed that horizontal writes are faster, since you can write multiple
  566. pixels at a time by using a 16 bit or 32 bit MOVE.
  567.  
  568. Eric Pinnell
  569. ...........................................................................
  570.  
  571. Fm: KGliner 70363,3672                         # 344953 
  572. To: E. Pinnell [CyberSim] 70031,435 (X)        Date: 30-Apr-93  15:38:42
  573.  
  574. Eric- normally, yes, but since you have to address each byte individually
  575. when texture mapping, 16 and 32 bit moves don't really help.
  576.  
  577.    Kevin
  578. ...........................................................................
  579.  
  580. Fm: John Dlugosz [ViewPoint] 70007,4657        # 344356 
  581. To: Lutz Kretzschmar 100023,2006 (X)           Date: 29-Apr-93  18:37:59
  582.  
  583. The line walkers sounds like what I was thinking of for simple magnification
  584. and reduction.  It would tell you which rows and colums to doplicate (or
  585. remove).  Stretching and not just scaling is more difficult.
  586.  
  587. I don't really follow your method.  Does it not provide for arbitrary
  588. stretching, or only for rotation and magnification?
  589.  
  590. --John
  591. ...........................................................................
  592.  
  593. Fm: Hans Peter Rushworth 100031,473            # 344467 
  594. To: John Dlugosz [ViewPoint] 70007,4657 (X)    Date: 29-Apr-93  20:33:09
  595.  
  596. John,
  597.  
  598. That program I sent you performs exactly the image mapping operation you are
  599. talking about. Try it out, and, if this does what you want, I'm willing to
  600. explain the method I used. The only difference is that it will Gouraud shade
  601. (and now dither) the bitmap as well as just "map" it.
  602.  
  603. The main limitiation is that it does not deal with perspective
  604. foreshortening. This is because it essentially is a 2D mapping which is
  605. performed after a 3D perspective transformation.
  606.  
  607. The method is very simple, but is quite hard to explain in a short message.
  608.  
  609. Peter.
  610. ...........................................................................
  611.  
  612. Fm: KGliner 70363,3672                         # 344273 
  613. To: John Dlugosz [ViewPoint] 70007,4657 (X)    Date: 29-Apr-93  16:19:34
  614.  
  615. John-  yes, that's more or less what I have in mind.  The biggest key is to
  616. remove the waste-- ie. you never want to draw more than one pixel to the same
  617. location on the screen.  How this is done with non-vertical/ non-horizontal
  618. line draws I don't know....
  619.  
  620.    Kevin
  621. ...........................................................................
  622.  
  623. Fm: John Dlugosz [ViewPoint] 70007,4657        # 344357 
  624. To: KGliner 70363,3672 (X)                     Date: 29-Apr-93  18:38:08
  625.  
  626. I think the best method would be to scan over the dest shape, one pixel at a
  627. time.  Each pixel gets a value from the source.  This guerentees you get
  628. every pixel exactly once, and you arrange for a nice order for them, too. 
  629. Mapping each dest location into the bitmap location is the tricky part.  I
  630. imagine an efficient incremental algorithm can be generated.
  631.  
  632. That is, as I move left-to-right in the screen image (which looks like a
  633. distorted diamond or kite perhaps), I need to move diagonally in the texture
  634. map, as well as change the rate of motion through it.  So I have 4 constants,
  635. dx, dy, ddx, and ddy.  I take the current x,y pixel, then do x+=dx; dx+=ddx;
  636. and likewise for the y's.  The hard part is coming up with the constants,
  637. which is done once per row, and even _those_ might be generated incrementally
  638. from the previous row.
  639.  
  640. What do you think?
  641.  
  642. --John
  643. ...........................................................................
  644.  
  645. Fm: Lutz Kretzschmar 100023,2006               # 345417 
  646. To: KGliner 70363,3672 (X)                     Date: 01-May-93  08:49:29
  647.  
  648. I had to a lot of work on getting the results to be of good quality. I used
  649. code from Graphics Gems I for scan converting polygons, it handled the
  650. corners pretty well. I never got any distortion that way and I can't really
  651. imagine where it came from. What did the distortion look like?
  652.  
  653. > What I ended up doing was running a diagonal ) line through the
  654. > destination polygon and horizontal lines through the source bitmap.
  655. Wow. Surely this would require a special linewalker for the diagonals, to
  656. cover every pixel. And the linewalker of the destination map would not be
  657. stepping in single step increments.
  658.  
  659. I guess what I'm trying to say is that the polygon linewalker is the
  660. *controlling* walker that defines how many steps the bitmap walker should
  661. take. Doing it the other way round may do polygon pixels more than once (if
  662. the imagemap is bigger than the polygon) or skip pixels (if it's smaller).
  663.  
  664. > Oh-- for this approach I also switched to using opposite edges (ie. run my
  665. > line walkers from corner A to corner D and from corner B to corner C
  666. I think I understand what you mean. Naturally one always uses opposite edges,
  667. but in my case I'm going through a polygon in screen space, where adjacent
  668. edges can make a scanline, whereas you were going through a
  669. coordinate-system-adjusted bitmap (i.e. unrotated). This would require using
  670. AD and BC in your example.
  671.  
  672. You're right about vertical lines, but on the hardware I was using (not VGA)
  673. there was a *much* larger calculation overhead for the next scanline.
  674. Horizontal scan-conversion just seems more natural to me, I guess<g>. But if
  675. it's better for vertical stuff, that'd be better.
  676.  
  677. If you ever discuss how this relates to hidden surface removal, let me
  678. know<g>. I would guess you could interpolate the distance on a vertical line
  679. as it approaches the eye. Whereas horizontal approached would need a true
  680. Z-buffer approach. Hmm, but then so would vertical lines. OK, maybe not<g>.
  681.  
  682. - Lutz
  683. ...........................................................................
  684.  
  685. Fm: KGliner 70363,3672                         # 346768 
  686. To: Lutz Kretzschmar 100023,2006 (X)           Date: 03-May-93  01:05:10
  687.  
  688. Lutz-  the problems you raise regarding the method I used for texture mapping
  689. were among the many reasons I abandoned that approach (and, more or less
  690. shelved it for a future product).  I ended up doing texture mapping only to
  691. polygons whose left and right edges were vertical (a la Wolfenstein 3d),
  692. something that was suitable for my purposes and much more straightforward to
  693. code.
  694.  
  695.     I was going to talk about the hidden-surface removal stuff tonight, but
  696. I'm too tired to explain it clearly.  I'll try to post something about it
  697. tomorrow. 
  698.  
  699.     Kevin
  700. ...........................................................................
  701.  
  702. Fm: Lutz Kretzschmar 100023,2006               # 345416 
  703. To: John Dlugosz [ViewPoint] 70007,4657 (X)    Date: 01-May-93  08:49:16
  704.  
  705. John,
  706.  
  707. the way I did it was to assign a coordinate system for the texture map to the
  708. polygon (I always convert four-sided polygons). So, for example, (using my
  709. ASCII drawing) the point A is (0,0), B is (1,0), C is (0,1) and D is (1,1).
  710. Setting up the line-walkers is simple interpolation, right? Only special
  711. thing about the linewalkers is that they always do a step in Y. This maps the
  712. bitmap to the polygon 1 to 1. I then put a 3x3 matrix transform between the
  713. mapping of the polygon points and the texture points. So, if translating by
  714. (0.5,0) A will be at (0.5,0), B at (0.5,1) etc. The matrix is built by
  715. concatenating translation, rotation or scaling as in normal 3D work. Then
  716. transform the points (of the texture map (0..1)) at the corners through the
  717. matrix and use these values to interpolate the starting conditions of the
  718. linewalkers. 
  719.  
  720. For the scan-conversion, I used an adapted version of the code in Graphics
  721. Gems I (pg. 76 "Fast anti-aliasing polygon scan conversion", by Jack C.
  722. Morrison), since I needed to do anti-aliasing, too (like I said, high quality
  723. had priority over speed).
  724.  
  725. - Lutz
  726. ...........................................................................
  727.  
  728. Fm: John Dlugosz [ViewPoint] 70007,4657        # 345473 
  729. To: Lutz Kretzschmar 100023,2006 (X)           Date: 01-May-93  10:43:09
  730.  
  731. That is pretty much was I was doodling yesterday.  Given 4 sides, can find
  732. the proportional position along the sides and use that to draw a line through
  733. the source bitmap.  However, I don't think that will show perspective right. 
  734. I'll see how it turns out.
  735.  
  736. --John
  737. ...........................................................................
  738.  
  739. Fm: Lutz Kretzschmar 100023,2006               # 346134 
  740. To: John Dlugosz [ViewPoint] 70007,4657 (X)    Date: 02-May-93  10:10:50
  741.  
  742. John,
  743.  
  744. yes, that won't work for perspective. I have no idea how to compensate for
  745. that, though.
  746.  
  747. - Lutz
  748. ...........................................................................
  749.  
  750. Fm: John Dlugosz [ViewPoint] 70007,4657        # 346224 
  751. To: Lutz Kretzschmar 100023,2006 (X)           Date: 02-May-93  12:18:12
  752.  
  753. I do.  The method allows for a quadradic in both x and y sides of the
  754. parametric eqn.  However, the hard part is coming up with all the parameters.
  755.  
  756. BTW, I've got a _very_ elegant way of using image maps, using features in the
  757. new version of ViewPoint.  I can better customize the polygon drawing engine
  758. on the fly, and can insert the texture mapping engine so it is called when a
  759. filled-polygon is being scan-converted.  Isn't OOP wonderful?
  760.  
  761. --John
  762. ...........................................................................
  763.  
  764. Fm: Lutz Kretzschmar 100023,2006               # 346845 
  765. To: John Dlugosz [ViewPoint] 70007,4657 (X)    Date: 03-May-93  05:34:23
  766.  
  767. Is the relationship really quadratic? Any way to use lookup tables for this
  768. to speed things up? I'd be interested in what kind of speed you're getting.
  769.  
  770. > Isn't OOP wonderful?
  771. Yup, I'll never turn back<g>.
  772.  
  773. - Lutz
  774. ...........................................................................
  775.  
  776. Fm: John Dlugosz [ViewPoint] 70007,4657        # 347261 
  777. To: Lutz Kretzschmar 100023,2006               Date: 03-May-93  20:13:29
  778.  
  779. The simple mapping I'm planning (if I _ever_ get to coding it) is linear. 
  780. Just a constant delta-x and delta-y, with about 4 lines of code to set it up.
  781.  
  782. The second degree will be used to provide perspective and other effects. But
  783. I have no idea how to set it up!  The simple way I'm going to do will match
  784. the way it will probably be used:  Draw a rectangle in a transformed
  785. coordinate system and it comes out rotated, scaled, and skewed into some
  786. arbitrary quadralateral.  However, the scaling will be uniform. When
  787. scan-converting the resulting shape, it will use the original scale object
  788. that was used to produce the shape to unscale the endpoints of the scan line,
  789. which will map to points on the edge of the texture square (same size as the
  790. logical square I drew). Back in the object's original coordinate system now,
  791. find chage in x and y between the two points, and divide that by the number
  792. of steps (the number of pixels in the scan-coverted row).  Then step through
  793. the pattern at this angle and record the pixels in a buffer which is then PUT
  794. on the screen. 
  795.  
  796. Easier to code than explain.
  797.  
  798. ViewPoint will handle the scan-converting of the polygon, and call upon my
  799. poly_fill_alg object to render the rows as it generates them.
  800.  
  801. --John
  802. ...........................................................................
  803.  
  804. Fm: Jez San @ Argonaut 72247,3661              # 346543 
  805. To: Lutz Kretzschmar 100023,2006 (X)           Date: 02-May-93  19:41:24
  806.  
  807. Do you anti alias your texture maps when they are scaled up larger than 1:1,
  808. eg: do your textures come out blocky when large or do you do bilinear
  809. interpolation to smooth out the chunky pixels?
  810.  
  811. -- Jez.
  812. ...........................................................................
  813.  
  814. Fm: Lutz Kretzschmar 100023,2006               # 346846 
  815. To: Jez San @ Argonaut 72247,3661 (X)          Date: 03-May-93  05:34:27
  816.  
  817. Jez,
  818.  
  819. in this program, I did not do interpolation, because the imagemaps are always
  820. much larger than the polygons. The program is used in the textile industry to
  821. change the fabric of upholstery on scanned images for example. The new fabric
  822. is mostly either scanned or drawn and will therefore always have enough
  823. detail. Mostly they have too much, which is why anti-aliasing was much more
  824. important. 
  825.  
  826. - Lutz
  827.  
  828. ___________________________ Subj: Filled Polygons ___________________________
  829.  
  830. Fm: Chris Lampton [GAMPUB] 76711,301           # 348393 
  831. To: Dave Roach 71333,706 (X)                   Date: 05-May-93  11:32:46
  832.  
  833. I suspect your diagram was reformatted by CIS, but I think you're describing
  834. a concave polygon (i.e. one with an internal angle greater than 180 degrees,
  835. creating an incursion into the interior). And, no, the algorithm doesn't work
  836. with concave polygons, only convex ones. But all concave polygons can be
  837. constructed from some combination of convex polygons, just as all polygons
  838. can be constructed from triangles (which are, of course, convex polygons). On
  839. the other hand, it works with some pretty complex convex polygons. I find
  840. that most concave polygons can be constructed from a very small number of
  841. n-sided convex polygons. 
  842.  
  843. If you've got a method for drawing fast concave polygons, I'd love to see it,
  844. though I gather it's proprietary. (Too bad!) I figured the speed gained by
  845. restricting the drawing code to convex polygons would offset the cost of
  846. decomposing concave polygons into convex ones.
  847.  
  848. --Chris
  849. ...........................................................................
  850.  
  851. Fm: John Dlugosz [ViewPoint] 70007,4657        # 348598 
  852. To: Chris Lampton [GAMPUB] 76711,301 (X)       Date: 05-May-93  17:53:52
  853.  
  854. I've profiled it, and found at the time that the cost of supporting standard
  855. polygons and not just convex ones is small.  I don't remember the details. 
  856. The cost of advancing each edge and testing for doneness is done for each
  857. edge, and is not any worse for a single edge.  SO they are slower to draw
  858. because they have more edges, but are not slower to support having 2*n edges
  859. instead of just 2.
  860.  
  861. --John
  862. ...........................................................................
  863.  
  864. Fm: Chris Lampton [GAMPUB] 76711,301           # 348849 
  865. To: John Dlugosz [ViewPoint] 70007,4657 (X)    Date: 05-May-93  22:54:03
  866.  
  867. One of these days I'll try my hand at a polygon fill routine that handles
  868. concave polygons to see how fast I can make it. Sounds like a bear to code,
  869. though.
  870.  
  871. --Chris
  872. ...........................................................................
  873.  
  874. Fm: John Dlugosz [ViewPoint] 70007,4657        # 349335 
  875. To: Chris Lampton [GAMPUB] 76711,301 (X)       Date: 06-May-93  18:56:32
  876.  
  877. No, it is quite simple.  So much so that it was not worth making a special
  878. function for simpler cases once I had the "do everything" version.
  879.  
  880.   for each scanline:
  881.      remove old edges    (a for() plus 4 lines in its body)
  882.      add new edges       (a for() plus 2 lines in its body)
  883.      draw between pairs of edges (2 lines, only because I support filling
  884.                              in two different ways.  So it is an if/else)
  885.      update edges for next scanline (a for() plus 2 lines in the body)
  886.  
  887. How different is that from a one-region function?  My list of active edges
  888. can have more than 2 items, that's all.  Everything else-- testing to see if
  889. an edge needs to be added or removed _here_, incrementing the edges, drawing
  890. a horizontal row, etc. is the same. This loop is 30 lines long, and includes
  891. a lot of vertical whitespace and unnecessary comments.  From the analasis
  892. above, the only real effect is each step is embedded in a for() loop.  For 2
  893. edges always, you would just have the statement repeated twice, one for each
  894. edge. For an arbitrary number of edges, I loop instead.
  895.  
  896.  
  897. --John
  898. ...........................................................................
  899.  
  900. Fm: Rasputin 71005,2524                        # 349644 
  901. To: John Dlugosz [ViewPoint] 70007,4657 (X)    Date: 07-May-93  01:08:49
  902.  
  903. I'm pretty much lost on your pseudocode... I call the function with a pointer
  904. to a list of points (sound logical eh?), and the function calculates the line
  905. points between each successive point and stores them in an array... then they
  906. get sorted by their y component, checking
  907.  for duplicate y values... then after they are sorted I use rep stosw to fill
  908. the line left to right... I am wondering how one would go about integrating
  909. and eliminating the sort function by just comparing the endpoints... I'm sure
  910. that it's extremely easy, but it just seems to elude me... I always end up
  911. with a case where the points are in come orientation that I hadn't thought
  912. of! I figured that someone on here might have some code that they would like
  913. to share... In return I'll upload a cool map maker with the source... any
  914. takers?!?!?? 
  915.                                 Entropy
  916. ...........................................................................
  917.  
  918. Fm: John Dlugosz [ViewPoint] 70007,4657        # 350069 
  919. To: Rasputin 71005,2524                        Date: 07-May-93  18:37:05
  920.  
  921. Instead of computing all the individual points in the line, the edge
  922. generates each point as needed.  The edges, not every single point, is sorted
  923. by the y value of its upper point.
  924.  
  925. What kind of map maker?
  926.  
  927. --John
  928. ...........................................................................
  929.  
  930. Fm: Dave Roach 71333,706                       # 348968 
  931. To: Chris Lampton [GAMPUB] 76711,301 (X)       Date: 06-May-93  06:19:51
  932.  
  933. There really isn't that much of a speed decrease, my routine requires an
  934. overhead of about 5k to get its optimal speed. By the way I'm still looking
  935. for a routine that can take verticies that make up a concave poly line
  936. drawing and giving me the outline... Any takers... <g>
  937.  
  938.  
  939. Dave
  940. ...........................................................................
  941.  
  942. Fm: Quentin Correll 70233,2264                 # 349185 
  943. To: Dave Roach 71333,706 (X)                   Date: 06-May-93  14:40:50
  944.  
  945. Hi Dave,
  946.  
  947.   >> By the way I'm still looking for a routine that can take verticies that
  948.   make up a concave poly line drawing and giving me the outline... Any
  949.   takers... <g><<
  950.  
  951.   Haven't we been here before?... ;-)
  952.  
  953.   This seems to be a slightly different statement of the problem we discussed
  954.   earlier.  When last you and I chatted I had the impression that you weren't
  955.   able to determine a "feature edge" to even arrive at the vertices.  Have
  956.   you made some progress?  How do you extract the vertices?
  957.  
  958.   Q
  959. ...........................................................................
  960.  
  961. Fm: John Dlugosz [ViewPoint] 70007,4657        # 348597 
  962. To: Dave Roach 71333,706 (X)                   Date: 05-May-93  17:53:47
  963.  
  964. Your picture came out reformatted.
  965.  
  966. The only difference to handle complex polys is to make sure the array of
  967. edges is still sorted after you increment all the edges.  It is not a major
  968. step-- after all, they had to be sorted once when you started, so the code is
  969. in there.
  970.  
  971. The difference between h-convex polys and standard polys (standard are
  972. allowed to be concave but don't self-intersect) is more significant. You have
  973. a single left edge list and a right edge list, and don't need to maintain
  974. multiple "fingers".
  975.  
  976. A triangle is even simpler yet-- only one edge change at most.
  977.  
  978. --John
  979. ...........................................................................
  980.  
  981. Fm: Rasputin 71005,2524                        # 348909 
  982. To: Chris Lampton [GAMPUB] 76711,301 (X)       Date: 06-May-93  01:07:01
  983.  
  984. Okay, I think I follow your description of how to do it. Now comes the part
  985. of actually trying to put it into code... 3d graphics definatly makes for
  986. interesting algorithms. thanks again for your help. 
  987.  
  988. ___________________________ Subj: Ghourad Shading ___________________________
  989.  
  990. Fm: Ed Goldman 72630,2763                      # 364901 
  991. To: all                                        Date: 29-May-93  12:11:49
  992.  
  993. I've been thinking about how to go about Ghourad Shading a polygon surface.
  994. I've got some ideas on this and questions regarding the vector math (I'm very
  995. rusty on the math -- haven't used it since high school).
  996.  
  997. It seems to me that the key to doing Ghourad Shading, and the most time
  998. consuming, is to obtain the unit vector normal for each vertix in the object.
  999. Once you have that it looks like calculating the intensity of each pixel
  1000. within the polygon in the drawing function is fairly straightforward.  It
  1001. looks like the best way to handle this is to calculate a point in object
  1002. coordinates which represents this unit normal for each vertix when the object
  1003. is loaded and initialized.  These points go thru the same translations as the
  1004. vertices when going from object->world->view. This may double the number of
  1005. points that must be translated per frame, but the alternative of calculating
  1006. the unit vertix normal on the fly seems much worse.
  1007.  
  1008. Now the math.  The vertix normal is the average of all polygon normals that
  1009. the vertix is part of.  So the first step is to find each face the vertix
  1010. sits on and calculate the normal for that face.  The normal for each face is
  1011. the cross-product of any 2 vector edges on the face radiating from the same
  1012. point -- I think I understand the math here.  Now here's where I'm not
  1013. entirely sure of the math. If the vertix is on 3 faces whose normal vectors
  1014. are A, B, and C. To get the vertix normal (N) do:
  1015.  
  1016. N.x = (A.x + B.x + C.x)/3;  N.y = (A.y + B.y + C.y)/3;  N.z = (A.z + B.z +
  1017. C.z)/3;
  1018.  
  1019. (Is this how vectors average?)
  1020.  
  1021. Now scale this to a unit normal and find the point in object space that
  1022. represents this:
  1023.  
  1024.  length = sqrt( N.x*N.x + N.y*N.y + N.z*N.z);
  1025.  UNormPoint.x = ObjectVert.x +
  1026.                         N.x/length;  /* x component distance from vertix */
  1027.  UNormPoint.y = ObjectVert.y +
  1028.                         N.y/length;  /* y component distance from vertix */
  1029.  UNormPoint.z = ObjectVert.z +
  1030.                         N.z/length;  /* z component distance from vertix */
  1031.  
  1032. Does this all hang together?  Are my basic assumptions about Ghourad shading
  1033. correct?  All comments appreciated ....
  1034.  
  1035. -edg-
  1036. ...........................................................................
  1037.  
  1038. Fm: Hans Peter Rushworth 100031,473            # 365432 
  1039. To: Ed Goldman 72630,2763 (X)                  Date: 30-May-93  10:42:25
  1040.  
  1041. Couple of points Ed,
  1042.  
  1043. For Gouraud shading *static* objects, you are really only concerned with the
  1044. vertex intensities (which you calculate from the average of the vertex
  1045. normals). If the light source is fixed wrt the surface, (say a mountain face
  1046. lit by the sun), then you don't need to re-evaluate the vertex intensities
  1047. every frame. Whatever your viewing position, the intensity will be the same.
  1048.  
  1049. For moving objects you don't *need* to recalculate the surface normals, just
  1050. the vertex normal. This you do by transforming the original vertex normal
  1051. with the rotational 3x3 part of the viewing transformation matrix. If you do
  1052. that you don't have to re-normalise the normal, so all you are left with is
  1053. the calculation of the vertex intensity, which is a simple dot product of the
  1054. normalised light source vector: In other words 
  1055.  
  1056.    intensity = light.x*(tm[0][0]*ovn.x + tm[0][1]*ovn.y + tm[0][2]*ovn.z) +
  1057.                light.y*(tm[1][0]*ovn.x + tm[1][1]*ovn.y + tm[1][2]*ovn.z) +
  1058.                light.z*(tm[2][0]*ovn.x + tm[2][1]*ovn.y + tm[2][2]*ovn.z);
  1059.  
  1060.    where "light" is the normalised light source vector
  1061.          "ovn"   is the original vertex normal (IOW the normal you get
  1062.                  for the untransformed object (calculated once))
  1063.          "tm"    is the rotation part of the matrix (no scaling terms)
  1064.  
  1065. To precalculate the ovn, you proceed as you suggested. remember that a vector
  1066. indicates direction only - you don't need to add your ObjectVert to the
  1067. normalised vector - doing so will give an incorrect result (assuming the
  1068. light source is very far away). I'll summarise this in case others are
  1069. interested: 
  1070.  
  1071.    surface normal = normalised cross product of 2 vectors along 2 edges of
  1072.                     the polygon (v0,v1,v2 are position vectors):
  1073.  
  1074.    sn.x = (v1.y - v0.y)*(v2.z - v1.z) - (v1.z - v0.z)*(v2.y - v1.y);
  1075.    sn.y = (v1.z - v0.z)*(v2.x - v1.x) - (v1.x - v0.x)*(v2.z - v1.z);
  1076.    sn.z = (v1.x - v0.z)*(v2.y - v1.y) - (v1.y - v0.y)*(v2.x - v1.x);
  1077.  
  1078.                     to normalise:
  1079.                     length = sqrt(sn.x*sn.x + sn.y*sn.y + sn.z*sn.z);
  1080.                     sn.x /= length;
  1081.                     sn.y /= length;
  1082.                     sn.z /= length;
  1083.  
  1084.    vertex normal = sum of surface normals / n
  1085.                    ovn.x = (sn[1].x + sn[2].x + ... sn[n].x)/n;
  1086.                    ovn.y = (sn[1].y + sn[2].y + ... sn[n].y)/n;
  1087.                    ovn.z = (sn[1].z + sn[2].z + ... sn[n].z]/n;
  1088.  
  1089. Phew!
  1090.  
  1091. Other points (for interest only)
  1092.  
  1093. The surface normals are useful for performing backface removal (take dot
  1094. product of the normal with the vector from the origin to any vertex on the
  1095. polygon, and look at it's sign), and in this instance you would re-calculate
  1096. or transform stored surface normals every frame anyway, so you may find that
  1097. calculating the vertex normal is faster if you just perform the averaging
  1098. step on the already transformed surface normals rather than transforming the
  1099. previous vertex normals (fewer multiplies). Either way should work, depending
  1100. on the organisation of your data. Remember that if a vector is normalised,
  1101. and you use the unscaled upper-left 3x3 part of the matrix (which are 3 sets
  1102. of normal vectors), then you don't need to normalise the product, which can
  1103. save you un-necessary square roots and other nasties. 
  1104.  
  1105. Hope that helps
  1106.  
  1107. Peter.
  1108. ...........................................................................
  1109.  
  1110. Fm: Ed Goldman 72630,2763                      # 366079 
  1111. To: Hans Peter Rushworth 100031,473 (X)        Date: 31-May-93  11:45:51
  1112.  
  1113. Thanks Peter!
  1114.  
  1115. Seems like the only real mistake I made in the math was adding the vertex
  1116. normal x, y, and z components to the vertex points (I thought I needed a
  1117. *point* in object space which corresponded to the vertex normal, and that
  1118. this point would need to be translated with the matrices along with the
  1119. object's verteces).
  1120.  
  1121. A question about your reply: If I've already got scaled unit surface normals
  1122. for all faces of an object built into the object structure (which I was
  1123. already planning to do for backface removal), then getting the vertex unit
  1124. normal is simply a matter of averaging all these normals for the faces the
  1125. vertex sits on?  I thought I'd still have to scale the vertex normal to a
  1126. unit vector after averaging which is why I was planning on storing and
  1127. translating vertex normals as well -- so that I'd only have to do the scaling
  1128. of the vector, which involves a sqrt(), once up front when the object is
  1129. loaded and init'd. If all I have to do is average surface unit normals, then
  1130. it seems I don't have to bother maintaining and translating vertex normals in
  1131. the object. 
  1132.  
  1133. -ed-
  1134. ...........................................................................
  1135.  
  1136. Fm: Hans Peter Rushworth 100031,473            # 366133 
  1137. To: Ed Goldman 72630,2763 (X)                  Date: 31-May-93  13:02:01
  1138.  
  1139. Ed,
  1140.  
  1141. >> I thought I needed a *point* in object space which corresponded to the
  1142. vertex normal, and that this point would need to be translated with the
  1143. matrices along with the object's verteces.
  1144.  
  1145. That might still work, but after you have transformed the vertepr= mal point,
  1146. you would need to subtract from the new point the transform of the point you
  1147. orginally added to it to get vertex normal. The surface and vertex normals
  1148. indicate *directions* and not *positions*. If you normalise a vector, any
  1149. position information is lost, and you retain only the direction information.
  1150.  
  1151. >> question...getting the vertex unit normal is simply a matter of averaging
  1152. all the [surface] normals for the faces the vertex sits on?
  1153.  
  1154. No, sorry, I made a mistake, that isn't true, you would have to normalise the
  1155. average vector to make the vertex normal. I missed out a few steps (see
  1156. below), and well spotted <g>. You could omit the division step during
  1157. averaging, so the vertex vector is the *sum* of the associated surface
  1158. normals, and the vertex normal is the vertex vector divided by the length of
  1159. the vertex vector. but... 
  1160.  
  1161. >> If all I have to do is average surface unit normals, then it seems I don't
  1162. have to bother maintaining and translating vertex normals in the object.
  1163.  
  1164. If you would still like to do that, there is an easy way out! What you do
  1165. (during initialisation) is take the initial *summed* vertex vector (before
  1166. you would normalise it to be a vertex normal), and work out it's length. Now
  1167. store the length (not the vertex normal) in with the object. When you come to
  1168. work out the transformed vertex normal, sum the transformed surface normals
  1169. and divide each component of the result by the stored length (if you prefer,
  1170. multiply it by 1/length). That should effect the generation and normalisation
  1171. of the vertex normal, on the fly, without a square root or extra
  1172. transformations. 
  1173.  
  1174. (I think I got out of that one <g>)
  1175.  
  1176. Peter.
  1177. ...........................................................................
  1178.  
  1179. Fm: Ed Goldman 72630,2763                      # 366390 
  1180. To: Hans Peter Rushworth 100031,473 (X)        Date: 31-May-93  19:07:50
  1181.  
  1182. Peter,
  1183.  
  1184. Thanks.  I see what you're getting at, but I'm a bit confused.  Are you
  1185. saying that an average of surface normals never needs to be done to get the
  1186. vertex normal, just a summation and div by precalc'd length?
  1187.  
  1188. Looks like what you're saying are these steps:
  1189.  
  1190. 1) Sum X, Y, Z components of surface normals.
  1191. 2) get length by sqrt( X^2 + Y^2 + Z^2) where X,Y,Z are the summed values.
  1192. Store this length with each vertex. 3) When it's time to draw the frame,
  1193. after the rotation matrix has been applied to the normals, just sum the
  1194. surface normals and div by stored length. This gives the vertex normal.
  1195.  
  1196. If that's the way it works, great!
  1197.  
  1198. One more thing, just about terminology: A surface normal, for instance, is a
  1199. vector perpendicular to the plane.  A *unit* surface normal would be vector
  1200. where length = 1.  When you say "normalize a normal" does that mean scaling a
  1201. normal to a unit normal?
  1202.  
  1203. I really should have paid more attention in math class <g> ....
  1204.  
  1205. -ed-
  1206. ...........................................................................
  1207.  
  1208. Fm: Hans Peter Rushworth 100031,473            # 366783 
  1209. To: Ed Goldman 72630,2763 (X)                  Date: 01-Jun-93  09:23:16
  1210.  
  1211. Ed,
  1212.  
  1213. By multiplying (or dividing) a vector by a scalar you don't change it's
  1214. direction. so the vectors (1,2,3) and (2,4,6) and (0.1,0.2,0.3) all point in
  1215. the same direction. The vector (0,0,0) and multiplying a vector by 0 are
  1216. special cases that must be avoided. When you average (as opposed to summing)
  1217. vectors the result only differs in it's length, not it's direction. So for
  1218. the average of 3 vectors, the division by 3 is superflous if all you want at
  1219. the end is a "length 1" vector.
  1220.  
  1221.    v = (a+b+c)/3; v /= |v|;     ==     v = (a+b+c); v /= |v|;
  1222.  
  1223.    because (v/3) / |v/3| ==  (v / |v|) * (3 / 3)    ==    v / |v|
  1224.  
  1225. I use "normalising" to imply making a vectors length equal to 1. Having all
  1226. the vectors the *same length* is important if you intend to add them
  1227. together, and having them all *length 1* is useful if you use the vectors in
  1228. dot products eg: 
  1229.  
  1230.    cos(theta) = a.b/|a||b|
  1231.  
  1232. if the vectors are "length 1" already this reduces to
  1233.  
  1234.    cos(theta) = a.b/(1*1) = a.b
  1235.  
  1236. similarly for cross products and lots of other vector algebra.
  1237.  
  1238. Remember also that a *rotation* matrix transformation applied to a vector
  1239. doesn't effect the length of the vector, only the direction.
  1240.  
  1241. >> Are you saying that an average of surface normals never needs to be done
  1242. to get the vertex normal, just a summation and div by precalc'd length?
  1243.  
  1244. Yes, You have a set of original surface normals, you add them up and get a
  1245. vector which is length L. However you rotate the normals, you may get a
  1246. vector sum pointing a different direction, but the length will always be L.
  1247.  
  1248. >>
  1249.    1) Sum X, Y, Z components of surface normals. [this sum is a vector the
  1250.       same length however the surface normals are oriented]
  1251.    2) get length by sqrt(X^2 + Y^2 + Z^2) where X,Y,Z are the summed
  1252.       values. Store this length with each vertex. [Now you know how to
  1253.       "normalise" the vertex normal]
  1254.    3) When it's time to draw the frame, after the rotation matrix has been
  1255.       applied to the normals, just sum the surface normals [to get the
  1256.       direction of the vertex normal] and div by stored length. [to make
  1257.       it a "normalised" vector] This gives the vertex normal.
  1258.  
  1259. Thats it.
  1260.  
  1261. >> about terminology:
  1262.  
  1263. Not sure, a normal vector might mean any length vector normal to a plane, and
  1264. "normalising" meant to imply making a vector length 1 is perhaps bad use of
  1265. terminology on my part. I tend to confuse the term "unit" with vectors like
  1266. (0,1,0) which are often also described as "base" vectors (ie (1,0,0), (0,1,0)
  1267. and (0,0,1) form a "basis" for spanning R3).
  1268.  
  1269. >> I really should have paid more attention in math class <g> ....
  1270.  
  1271. Well, if they applied the vector algebra to Gouraud shading and computer
  1272. graphics, I think both of us would be much more knowledgable about it.
  1273. Addressing enquiries like yours helps keep what little there is from getting
  1274. too rusty to be of use. <g>
  1275.  
  1276. Peter.
  1277. ...........................................................................
  1278.  
  1279. Fm: Hans Peter Rushworth 100031,473            # 365438 
  1280. To: Ed Goldman 72630,2763 (X)                  Date: 30-May-93  10:47:57
  1281.  
  1282. I forgot...
  1283.  
  1284. When you 3D clip the polygons that are to be Gouraud shaded, you must
  1285. remember to push and possibly create interpolated vertex intensities along
  1286. with the the vertex points. This is exactly analogous to the treatment of the
  1287. points position components. If you fail to do this you will get strange
  1288. results as the objects move out of the view window. (I guess that is an
  1289. obvious point). 
  1290.  
  1291. Peter.
  1292. ...........................................................................
  1293.  
  1294. Fm: Steve Ringley 73727,1202                   # 366142 
  1295. To: Ed Goldman 72630,2763 (X)                  Date: 31-May-93  13:23:47
  1296.  
  1297. I don't know too much about it, but if you have not already, download
  1298. LATHE.ZIP from Lib 15 of the Zenith forum.  It does Ghourad shading, and the
  1299. $30 registration includes C source code.
  1300. ...........................................................................
  1301.  
  1302.